#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<int> getmax(vector<int>& nums, int t)
{
    vector<int> ret;
    for (auto i : nums)
    {
        while (ret.size() && ret.back() < i && t)
        {
            ret.pop_back();
            t--;
        }
        ret.push_back(i);
    }
    while (t--)  ret.pop_back();
    return ret;
}

int compare(vector<int>& nums1,int d1, vector<int>& nums2,int d2)
{
    while (d1 < nums1.size() && d2 < nums2.size())
    {
        int dif = nums1[d1] - nums2[d2];
        if (dif != 0)    return dif;
        d1++, d2++;
    }
    return (nums1.size() - d1) - (nums2.size() - d2);
}

vector<int> merge(vector<int>& nums1, vector<int>& nums2)
{
    int n = nums1.size(), m = nums2.size();
    if (n == 0)  return nums2;
    if (m == 0)  return nums1;

    int len = n + m;
    vector<int> ret;
    int d1 = 0, d2 = 0;
    while (d1 < n && d2 < m)
        if (compare(nums1, d1, nums2, d2) > 0)
            ret.push_back(nums1[d1++]);
        else ret.push_back(nums2[d2++]);
    while (d1 < n)   ret.push_back(nums1[d1++]);
    while (d2 < m)   ret.push_back(nums2[d2++]);
    return ret;
}

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    int n = nums1.size(), m = nums2.size();
    vector<int> res(k);
    int del = n + m - k;
    int start = max(0,del - m), end = min(del, n);
    for (int i = start; i <= end; i++)
    {
        auto t1 = getmax(nums1, i);
        auto t2 = getmax(nums2, del - i);
        auto cur = merge(t1, t2);
        if (compare(res,0, cur,0) < 0)
            res.swap(cur);
    }
    return res;
}

int main()
{
    auto cmp = [](int x, int y)->bool {
        return x < y;
    };
    priority_queue<int, vector<int>,cmp> pq;
    vector<int> v1 = { 3,9 };
    vector<int> v2 = { 8,9 };
    maxNumber(v1, v2, 3);
    return 0;
}